package pri.zjy.string;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangjy
 * @description 同构字符串
 * <p>
 * 给定两个字符串 s 和 t ，判断它们是否是同构的。
 * <p>
 * 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
 * <p>
 * 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
 * @date 2025/4/1 19:13
 */
public class IsIsomorphic_205 {

    public static void main(String[] args) {
        IsIsomorphic_205 isIsomorphic205 = new IsIsomorphic_205();
        String s = "badc";
        String t = "baba";
        System.out.println(isIsomorphic205.isIsomorphic(s, t));
        System.out.println(isIsomorphic205.isIsomorphic2(s, t));
    }

    /**
     * 官解-哈希；
     * 与个解区别是：
     * 1.把return false的判断条件都整合到一起。
     * 2.使用char的包装类Character。
     */
    public boolean isIsomorphic2(String s, String t) {
        Map<Character, Character> s2t = new HashMap<Character, Character>();
        Map<Character, Character> t2s = new HashMap<Character, Character>();
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            char x = s.charAt(i), y = t.charAt(i);
            if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
                return false;
            }
            s2t.put(x, y);
            t2s.put(y, x);
        }
        return true;
    }

    /**
     * 个解-哈希；
     * <p>
     * 思路：既要满足s与t有唯一映射，也要满足t与s有位移映射
     * <p>
     * 分析：
     * <p>
     * 由题可知，同构要满足：
     * 1）s的字符 与 t的字符 有唯一映射关系；
     * 2）t的字符 也要与 s的字符 有唯一映射关系。
     * <p>
     * 如，s = "badc"，t = "baba"； 就不满足第二点，t的字符b 与 s的字符b、d都出现了映射关系。
     */
    public boolean isIsomorphic(String s, String t) {
        // s、t字符映射关系
        // key = s的char，value=t的char
        Map<String, String> sTMap = new HashMap<>();
        // key = t的char，value=s该字符是否映射过
        Map<String, Boolean> tMap = new HashMap<>();
        // 遍历是否同构
        for (int i = 0; i < s.length(); i++) {
            String key = String.valueOf(s.charAt(i));
            String value = String.valueOf(t.charAt(i));
            if (sTMap.containsKey(key)) {
                // 判断是否为同一映射（s映射t）
                // 若存在key，但是value不同，表明不是同构，返回false;
                if (!sTMap.get(key).equals(value)) return false;
            } else {
                // 判断是否为同一映射（t映射s）
                // 判断s的相同字符是否映射到t的同一个字符上（如果tMap有该键，表明t的这个字符已经被s的字符映射过，现在key再次映射就会覆盖）
                if (tMap.containsKey(value)) {
                    return false;
                }
                // key-value该映射关系首次出现，则记录到sTMap
                sTMap.put(key, value);
                tMap.put(value, true);

            }
        }

        return true;
    }

}
